Search results for "finite model theory"

showing 2 items of 2 documents

A NOTE ON THE ASYMPTOTIC PROBABILITIES OF EXISTENTIAL SECOND-ORDER MINIMAL GÖDEL SENTENCES WITH EQUALITY

1995

The minimal Gödel class is the class of first-order prenex sentences whose quantifier prefix consists of two universal quantifiers followed by just one existential quantifier. We prove that asymptotic probabilities of existential second-order sentences, whose first-order part is in the minimal Gödel class, form a dense subset of the unit interval.

CombinatoricsDiscrete mathematicsPrefixFinite model theoryClass (set theory)Quantifier (logic)Dense setSecond-order logicExistential quantificationComputer Science (miscellaneous)MathematicsUnit intervalInternational Journal of Foundations of Computer Science
researchProduct

The Descriptive Complexity Approach to LOGCFL

1998

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…

FOS: Computer and information sciencesFinite model theoryUnary operationComputer Networks and Communicationsautomata and formal languages0102 computer and information sciencesComputational Complexity (cs.CC)Computer Science::Computational ComplexityArityDescriptive complexity theory01 natural sciencesTheoretical Computer ScienceComputer Science::Logic in Computer ScienceNondeterministic finite automaton0101 mathematicsLOGCFLMathematicsDiscrete mathematicscomputational complexityApplied Mathematics010102 general mathematicsdescriptive complexityNondeterministic algorithmComputer Science - Computational Complexityfinite model theoryQuantifier (logic)Computational Theory and Mathematics010201 computation theory & mathematicsF.1.3Journal of Computer and System Sciences
researchProduct